package chapter15;

import java.util.*;

/**
 * * LIS:最长单调递增数组
 * * 思想：线性数组转矩阵
 * * 例如：
 * * X=[1,3,2,3,5,4]
 * * 0 1 3 2 3 5 4
 * * 1 1 1 1 1 1 1
 * * 3 2 2 1 1 1 1
 * * 2 2 2 2 1 1 1
 * * 3 2 2 3 3 1 1
 * * 5 2 3 3 4 4 1
 * * 4 2 3 4 4 4 4
 * *
 * * 路径图
 * * 0 1 3 2 3 5 4
 * * 1 1 1 1 1 1 1
 * * 3 0 1 0 0 1 1
 * * 2 0 0 1 1 1 1
 * * 3 0 0 0 1 1 1
 * * 5 0 0 0 0 1 0
 * * 4 0 0 0 1 0 1
 * *
 */
public class LIS {

    public static void printLIS(int[] x) {
        int m = x.length;
        // dp计算图
        int[][] c = new int[m + 1][m + 1];
        // 路径可达图
        int[][] p = new int[m][m];
        // 最长LIS的长度
        int maxLen = 0;
        // 本身也算一个可达
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= m; j++) {
                c[i][j] = 1;
            }
            if (i < p.length) {
                p[i][i] = 1;
            }
        }
        // 计算最长长度
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= i; j++) {
                if (x[i - 1] > x[j - 1]) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, c[i][j]);
                    p[j - 1][i - 1] = 1;
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        System.out.println("DP计算图" + Arrays.deepToString(c));
        System.out.println("路径图" + Arrays.deepToString(p));
        Set<List<Integer>> paths = new HashSet<>();
        for (int i = 0; i < p.length; i++) {
            dfs(p, x, i, i, new LinkedList<>(), paths);
        }
        System.out.println("AllPath" + paths);
        for (List<Integer> path : paths) {
            if (path.size() == maxLen) {
                System.out.println("MaxPath" + path);
            }
        }
    }

    private static void dfs(int[][] p, int[] x, int i, int j, LinkedList<Integer> path, Set<List<Integer>> paths) {
        // i 代表 小数
        // j 代表 大数
        // i-j 代表 从i到j,代表i小于等于j
        // 当p[i][j]不可达,则记录路径
//        if (p[i][j] == 0) {
//            if (path.size() > 0) {
//                paths.add(new ArrayList<>(path));
//            }
//            return;
//        }

        // 看j比谁小
        for (int k = 0; k < p.length; k++) {
            int n = x[k];
            if (p[j][k] == 1 && !path.contains(n)) {
                // 可达将路径放入
                path.add(n);
                dfs(p, x, j, k, path, paths);
                // 回溯
                path.removeLast();
            } else if (p[j][k] == 0) {
                paths.add(new ArrayList<>(path));
            }
        }

    }

    public static int[][] LISLength(int[] x) {
        int m = x.length;
        int[][] c = new int[m + 1][m + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= m; j++) {
                c[i][j] = 1;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= i; j++) {
                if (x[i - 1] > x[j - 1]) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                    System.out.println((i - 1) + "-" + (j - 1));
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        return c;
    }

    /**
     * 最长单调递增数组
     *
     * @param x
     * @return
     */
    public static List<Integer> LIS(int[] x) {
        int n = x.length;
        int[] dp = new int[n];
        int[] sub = new int[n];
        int maxIndex = -1;
        int max = -1;
        Arrays.fill(sub, -1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (x[i] > x[j]) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        sub[i] = j;
                        max = dp[i];
                        maxIndex = i;
                    }
                }
            }
        }
//        System.out.println(Arrays.toString(dp));
//        System.out.println(Arrays.toString(sub));
//        System.out.println(maxIndex);
//        System.out.println(max);

//        int[] r = new int[max + 1];
        List<Integer> r = new ArrayList<>();
        r.add(0, x[maxIndex]);
        while (maxIndex != -1) {
            int j = sub[maxIndex];
            if (j >= 0) {
                r.add(0, x[j]);
            }

            maxIndex = j;
        }

//        System.out.println(r);
        return r;
    }

    public static int[] LIS2(int[] x) {
        int n = x.length;
        List<Integer> lis = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (lis.size() == 0) {
                lis.add(x[i]);
            } else if (lis.get(0) > x[i]) {
                lis.set(0, x[i]);
            } else if (lis.get(lis.size() - 1) < x[i]) {
                lis.add(x[i]);
            } else {

                int left = 0;
                int right = lis.size() - 1;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (lis.get(mid) == x[i]) {
                        lis.set(mid, x[i]);
                        break;
                    }
                    if (lis.get(mid) > x[i]) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                    if (left == right) {
                        lis.set(left, x[i]);
                    }
                }

            }
        }

        int[] c = new int[lis.size()];
        for (int i = 0; i < lis.size(); i++) {
            c[i] = lis.get(i);
        }
        return c;
    }

}
